﻿// sortAlg.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
using namespace std;
class sortObj {
public:
	uint32_t key;
	sortObj(uint32_t k_) :key(k_) {}
	virtual ~sortObj(){}
	bool operator >(const sortObj &a) { return key > a.key; }
	bool operator >=(const sortObj &a) { return key >= a.key; }
	bool operator <(const sortObj &a) { return  key < a.key; }
	bool operator <=(const sortObj &a) { return key <= a.key; }
	bool operator ==(const sortObj &a) { return key == a.key; }

};
//模板函数
template<typename T>
void Bubble_sort(T &arry,int len) {
	int i, j;
	for (i = 0; i < len-1; i++) {
		for (j = 0; j < len - 1-i; j++) {
			if (arry[j] > arry[j + 1]) {
				swap(arry[j], arry[j+1]);
			}
		}
	}
}
template<class T>
void Select_sort(T &a, int len) {
	for (int i = 0; i < len; i++) {
		int minIdex = i;
		for (int j = i+1; j < len; j++) {
			if (a[j] < a[min]) {
				min = j;
			}
		}
		swap(a[i],a[minIdex]);
	}
}
template<typename T>
void merge(T &a,int l,int mid,int r,T &temp) {
	int i = l, j = mid + 1;
	int t = l;
	//合并两个有序数组
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			temp[t++] = a[i++];
		}
		else {
			temp[t++] = a[j++];
		}
	}
	while (i <= mid) {//左边的数组放入
		temp[t++] = a[i++];
	}
	while (j <= r) {
		temp[t++] = a[j++];
	}
	//拷贝数组
	for (int ii = l; ii <= r; ii++) {
		a[ii] = temp[ii];
	}
}
template<class T>
void Merge_sort(T &a, int l,int r,T &temp) {
	if (l < r) {
		int mid = l + (r - l) / 2;
		Merge_sort(a,l,mid,temp);//左边
		Merge_sort(a, mid + 1, r, temp);//右边
		merge(a, l, mid, r, temp);//左右归并
	}
	

}
template<class T>
void Merge_sort(T &a, int len) {
	T tem(a);//拷贝a 
	Merge_sort(a, 0, len - 1, tem);
}

template<typename T>
void Quick_sort(T &a,int left,int right) {
	if (left < right) {
		int i = left, j = right, x = a[left];
		while (i < j) {
			while (i < j&&a[j] >= x)//从右往左找
			{
				j--;
			}
			if (i < j) a[i++] = a[j];
			while (i<j && a[j]> x)//从左往右找
				i++;
			if (i < j) a[j--] = a[i];
		

		}
		a[i] = x;
		Quick_sort(a,left,i-1);
		Quick_sort(a, i + 1, right);
	}

}

int main()
{
    
	vector<int> a{ 2,5,3,1,6 };
	auto b = a;
	Bubble_sort(a,a.size());
	cout << "\nBubble_sort:";
	for (auto x : a) {
		cout << x << " ";
	}
	a = b;
	cout << "\nSelect_sort:";
	Select_sort(a,a.size());
	for (auto x : a) {
		cout << x << " ";
	}
	a = b;
	cout << "\nMerge_sort:";
	Merge_sort(a,a.size());
	for (auto x : a) {
		cout << x << " ";
	}
	a = b;
	cout << "\nQuick_sort:";
	Quick_sort(a,0,a.size()-1);
	for (auto x : a) {
		cout << x << " ";
	}


}


